package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * dp
 * 376. 摆动序列
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/16 14:14
 */
public class WiggleMaxLength {

    public static void main(String[] args) {
        WiggleMaxLength test = new WiggleMaxLength();
        // [1,1,7,4,9,2,5]   6
        int[] arr = {1,1,7,4,9,2,5};

        int i = test.wiggleMaxLength(arr);
        System.out.println(i);
    }

    public int wiggleMaxLength(int[] nums) {
        int length = nums.length;
        int[] a = new int[length];
        int[] b = new int[length];

        a[0] = 1;
        b[0] = 1;
        int item = nums[0];
        for (int i = 1; i < length; i++) {
            int num = nums[i];
            if (num > item) {
                a[i] = Math.max(b[i - 1] + 1, a[i - 1]);
                b[i] = b[i - 1];
            } else if (num < item) {
                b[i] = Math.max(a[i - 1] + 1, b[i - 1]);
                a[i] = a[i - 1];
            } else {
                a[i] = a[i - 1];
                b[i] = b[i - 1];
            }
            item = num;
        }
        return Math.max(a[length - 1], b[length - 1]);
    }

}
